#include <iostream>
#include <map>
#include <fstream>
#include <ctime>
#include <unistd.h>
#include <cstdlib>
#include <vector>
#include <ctype.h>
#include <cmath>
#include <omp.h>
#include <algorithm>

using namespace std;


typedef struct word
{
    string st;
    int occurrences;
};

int process_words(string st, map<string,int*> *map_words)
{
    map<string,int*>::iterator it;
    it = map_words->find(st);
    if(it != map_words->end())
        return 1;

    int middle = st.size()/2;
    int lpos = middle;
    string lst = st.substr(0, lpos);
    string rst = st.substr(lpos, string::npos);

    while(lpos > 0)
    {
        //Tenta encontrar o lado esquerdo da palavra
        if(lst.size() > 0)
        {
            it = map_words->find(lst);
            if(it != map_words->end())
                lst.clear();
            else
                lpos--;/*
            if(lst.size() > 10)
            {
                it = map_words_11plus->find(lst);
                if(it != map_words_11plus->end())
                    lst.clear();
                else
                    lpos--;
            }
            else if(lst.size() >= 5 && lst.size() <= 10)
            {
                it = map_words_6to10->find(lst);
                if(it != map_words_6to10->end())
                    lst.clear();
                else
                    lpos--;
            }
            else
            {
                it = map_words->find(lst);
                if(it != map_words->end())
                    lst.clear();
                else
                    lpos--;
            }*/
        }

        //Tenta encontrar o lado direito da palavra
        if(rst.size() > 0)
        {
            it = map_words->find(rst);
            if(it != map_words->end())
                rst.clear();
            /*
            if(rst.size() > 10)
            {
                it = map_words_11plus->find(rst);
                if(it != map_words_11plus->end())
                    rst.clear();
            }
            else if(rst.size() >= 5 && rst.size() <= 10)
            {
                it = map_words_6to10->find(rst);
                if(it != map_words_6to10->end())
                    rst.clear();
            }
            else
            {
                it = map_words->find(rst);
                if(it != map_words->end())
                    rst.clear();
            }*/
        }

        //Se encontrou as duas partes, retorna 1
        if(lst.size() == 0 && rst.size() == 0)
            return 1;
        //Senao, continua processando
        else
        {
            if(rst.size() > 0)
                rst = st.substr(lpos, string::npos);
            if(lst.size() > 0)
                lst = st.substr(0, lpos);
            else
                break;

        }
    }
    //Se não encontrou nem a primeira letra do lado esquerdo, para execucao
    if(lpos == 0)
        return 0;


    int rpos;
    if(rst.size() > 0)
    {
        rpos = middle+1;
        //Se a execucao nao parou, explora o lado direito
        while(rpos < st.size())
        {
            rst = st.substr(rpos, string::npos);

            it = map_words->find(rst);
            if(it != map_words->end())
            {
                rst.clear();
            }
            else
                rpos++;
            /*
            if(rst.size() > 10)
            {
                it = map_words_11plus->find(rst);
                if(it != map_words_11plus->end())
                {
                    rst.clear();
                }
                else
                    rpos++;
            }
            else if(rst.size() >= 5 && rst.size() <= 10)
            {
                it = map_words_6to10->find(rst);
                if(it != map_words_6to10->end())
                {
                    rst.clear();
                }
                else
                    rpos++;
            }
            else
            {
                it = map_words->find(rst);
                if(it != map_words->end())
                {
                    rst.clear();
                }
                else
                    rpos++;
            }*/

            if(rst.size() == 0)
            {
                break;
            }
        }
    }
    else
        rpos = lpos;

    if(rpos == st.size()-1)
        return 0;

    st = st.substr(lpos, (rpos-lpos));
    if(st.size() == 0)
        return 1;

    return process_words(st, map_words);
}


void read_map(map<string,int*> *m, const char *fname)
{
    ifstream f;
    f.open(fname);
    while(f.good())
    {
        string st;
        f >> st;
        if(st.size() > 0)
        {
            int *vn = (int*)malloc(3*sizeof(int));
            f >> vn[0];
            f >> vn[1];
            f >> vn[2];
            m->insert(pair<string,int*>(st, vn));
        }
    }
}

void read_pref_suf(vector<word*> *v, const char *fname)
{
    ifstream f;
    f.open(fname);
    while(f.good())
    {
        string st;
        f >> st;
        if(st.size() > 0)
        {
            word *new_word = new word();
            new_word->st = st;
            f >> new_word->occurrences;
            v->push_back(new_word);
        }
    }
}

void read_vector(vector<vector<string*> > *v)
{
    ifstream f;

    for(int i = 0; i < 45; i++)
        v->push_back(vector<string*>());

    f.open("vector_out.txt");
    while(f.good())
    {
        string st;
        f >> st;
        if(st.size() > 0)
        {
            string *aux = new string(st);
            v->at(st.size()-1).push_back(aux);
        }
    }
}

string generate_word(int size)
{

    vector<string> str_vec;
    int ceiling_ = ceil(((double)size/5));
    int floor_ = floor(((double)size/ceiling_));
    int amount[ceiling_];

    if(size > 5)
    {
        for(int i = 0; i < ceiling_; i++)
            amount[i] = floor_;
        for(int i = 0; i < (size-ceiling_*floor_); i++)
            amount[i]++;
    }
    else
        amount[0] = size;

    #pragma omp parallel for
    for(int j = 0; j < ceiling_; j++)
    {
        string str;
        for(int i = 0; i < amount[j]; i++)
        {
            int r;
            //'a'-'z'   -> 26 elementos
            r = rand()%26;
            r += 65;
            str += ((char)r);
        }
        str_vec.push_back(str);
    }

    string str;
    for(int i = 0; i < ceiling_; i++)
        str += str_vec.at(i);

    return str;
}



bool compare(word *a, word *b)
{
    return (a->occurrences > b->occurrences);
}
//bool myfunction (int i,int j) { return (i<j); }

int main(int argc, char *argv[])
{
    //Ponteiro para arquivo
    FILE *fp;
	//caracter usado para ler arquivo
	char c;
    //Mapa de palavras - ate 5 letras
    map<string,int*> map_words;
    //Mapas de palavras: de 6 a 10 letras, mais de 11 letras
    //map<string,int*> map_words_6to10, map_words_11plus;
    //Iterador
    map<string,int*>::iterator it;
    //Retorno de inserção
    pair<map<string,int*>::iterator,bool> ret;
    //tamanho máximo das palavras do texto
    int max = 0;
    //Stream para escrever em arquivos
    ofstream f;

    //Contador de palavras encontradas
    int found = 0;

    //vetor por tamanho de palavras
    vector<vector<string*> > words_by_size;

    //vetor DE tamanho de palavras
    vector<int> size_of_words;
    //Vetores de prefixos e sufixos
    vector<word*> prefixes, sufixes;


    cout << "Preprocessamento do arquivo... " << endl;

    srand(time(NULL));
	//abertura do arquivo
    fp = fopen("palavras.txt", "r");
    //preprocessa o arquivo
    do
    {
        string str;
        c = fgetc(fp);
        //Enquanto nao encontra um símbolo de sincronia, consome
        while(!isalpha(c) && c != EOF)
        {
            c = fgetc(fp);
        }
        //Se encontrou fim de linha, para a execucao do laco
        if(c == EOF)
            break;
        //Monta a palavra ate encontrar um simbolo nao permitido
        while((isalnum(c) || c == '-') && c != EOF)
        {
            str += toupper(c);
            c = fgetc(fp);
            while(isdigit(c) || c == '-')
            {
                c = fgetc(fp);
            }
        }
        //Se encontrou fim de linha, para a execucao do laco
        if(c == EOF)
            break;

        int strsize = str.size();
        //Aumenta o vetor se |palavra| > tamanho do vetor para |palavra|
        if(strsize > max)
        {
            for(int i = 0; i < (strsize-max); i++)
            {
                words_by_size.push_back(vector<string*>());
                size_of_words.push_back(0);
            }
            //Atribui |palavra| para o tamanho do vetor
            max = strsize;
        }
        int *vn = (int *)malloc(3*sizeof(int));
        vn[0] = vn[1] = vn[2] = 0;
        //Insere a palavra no mapa, se possível
        ret = map_words.insert(pair<string,int*>(str,vn));
        //Se foi possível, ret.second vale TRUE
        if(ret.second)
        {
            string *aux_str = new string(str);
            words_by_size[strsize-1].push_back(aux_str);
            size_of_words[strsize-1]++;
        }
        else
            free(vn);

    }while(c != EOF);

    //Limpa o mapa
    map_words.clear();
    //Reinsere os dados nos respectivos mapas, das palavras menores para as palavras
    //maiores, contabilizando corretamente a incidencia de prefixos e sufixos
    for(int i = 0; i < words_by_size.size(); i++)
    {
        for(int j = 0; j < words_by_size[i].size(); j++)
        {
            int *vn = (int *)malloc(3*sizeof(int));
            vn[0] = vn[1] = vn[2] = 0;
            string st = *words_by_size[i][j];
            map_words.insert(pair<string,int*>(st, vn));
            for(int k = i; k > 0; k--)
            {
                it = map_words.find(st.substr(0,k));
                if(it != map_words.end())
                    it->second[1]++;
            }
            for(int k = 1; k <= i; k++)
            {
                it = map_words.find(st.substr(k,i+1));
                if(it != map_words.end())
                    it->second[2]++;
            }
        }
    }

    f.open("map");
    //Insere todos os dados do mapa nos vetores de prefixos e sufixos - até 5 letras
    //Tambem escreve o arquivo correspondente
    for(it=map_words.begin(); it != map_words.end(); it++)
    {
        word *pref = new word();
        word *suf = new word();
        //Pega a string
        pref->st = suf->st = it->first;
        //Pega a incidencia de prefixos
        pref->occurrences = it->second[1];
        //Pega a incidencia de sufixos
        suf->occurrences = it->second[2];
        //Escreve o arquivo
        f << it->first << " " << it->second[0] << " " << it->second[1] << " " << it->second[2] << endl;
        prefixes.push_back(pref);
        sufixes.push_back(suf);
    }
    f.close();

    //Ordena os vetores por ocorrencia [palavras com mais incidencia primeiro]
    sort(prefixes.begin(), prefixes.end(), compare);
    sort(sufixes.begin(), sufixes.end(), compare);

    //Escreve o arquivo de prefixos
    f.open("prefix");
    int cnt = 0;
    while(prefixes.at(cnt)->occurrences > 0)
    {
        f << prefixes.at(cnt)->st << " " << prefixes.at(cnt)->occurrences << endl;
        cnt++;
    }
    //Remove as palavras que não tem incidencia como prefixo
    while(prefixes.size() > cnt)
        prefixes.erase(prefixes.begin()+cnt);
    f.close();

    //Escreve o arquivo de sufixos
    f.open("sufix");
    cnt = 0;
    while(sufixes.at(cnt)->occurrences > 0)
    {
        f << sufixes.at(cnt)->st << " " << sufixes.at(cnt)->occurrences << endl;
        cnt++;
    }
    //Remove as palavras que não tem incidencia como sufixo
    while(sufixes.size() > cnt)
        sufixes.erase(sufixes.begin()+cnt);
    f.close();

    f.open("vector_out.txt");
    for(int i = 0; i < words_by_size.size(); i++)
    {
        for(int j = 0; j < words_by_size[i].size(); j++)
            f << *words_by_size[i][j] << " ";
        f << endl;
    }
    f.close();

    cout << "Finalizado!" << endl << endl;

    //Geração de palavras aleatorias de 1 ate 5 letras
    //Para cada posicao do vetor, resolve todas as palavras
    #pragma omp parallel for reduction(+:found)
    //for(int i = 0; i < size_of_words.size(); i++)
    for(int i = 0; i < 5; i++)
    {
        //no. de palavras daquela posicao do vetor
        int n_words = size_of_words.at(i);
        //enquanto houver palavras,
        #pragma omp shared(n_words) schedule(dynamic) reduction(-:n_words)
        while(n_words > 0)
        {
            //gera uma palavra aleatoria do tamanho da posicao
            string word = generate_word(i+1);
            //tenta encontrar a palavra no mapa
            map<string,int*>::iterator it_w = map_words.find(word);
            //Se encontrar,
            if(it_w != map_words.end())
            {
                //e se a palavra ainda nao foi encontrada,
                if(it_w->second[0] == 0)
                {
                    //incrementa o valor de entrada
                    it_w->second[0]++;
                    //reduz o numero de palavras a encontrar
                    n_words--;
                    //incrementa o no. de paalvras encontradas
                    found++;
                }
            }
        }
    }
    cout << "Primeiras: found = " << found << endl;


    //Gera uma combinação de um prefixo + uma ou mais palavras
    for(int i = 0; i < prefixes.size(); i++)
    {
        //pega o sufixo
        string pref = prefixes.at(i)->st;
        //cout << "prefixo: " << pref << endl;
        //procura, pelo iterador, as palavras que começam com ele
        map<string,int*>::iterator it_p = map_words.upper_bound(pref);
        //avança aquelas que já foram encontradas
        while(it_p->second[0] == 1)
            it_p++;

        //Se ainda há ocorrências deste sufixo
        while(prefixes.at(i)->occurrences > 0)
        {
            while(it_p->first.size() <= 5)
                it_p++;

            //Se o prefixo mudou, encerra o laço (palavra nao sera encontrada)
            if(it_p->first.substr(0,pref.size()) != pref)
                break;
            //pega a palavra a ser encontrada
            string st = it_p->first;
            //cout << "palavra: " << st;
            //remove o prefixo
            st = st.substr(pref.size(), string::npos);
            //processa a palavra, tentando decompo-la e achar cada cada parte,
            //formando a palavra completa
            if(process_words(st, &map_words) == 1)
            {
                if(it_p->second[0] == 0)
                {
                    //cout << " - encontrada" << endl;
                    it_p->second[0]++;
                    prefixes.at(i)->occurrences--;
                    found++;
                }
            }
            //cout << endl;
            //else cout << " - NAO encontrada" << endl;
            //encontrando a palavra ou nao, avanca o iterador para a proxima palavra
            it_p++;
            //se o iterador estorou a capacidade do map, para a execucao
            if(it_p == map_words.end())
                break;
        }
    }
    cout << "found = " << found  << " / rep = " << rep << endl;

    f.open("out.txt");
    //Impressão do mapa
 	for(it=map_words.begin(); it != map_words.end(); it++)
        f << it->first << " -> " << it->second[0] << ", "
          << it->second[1] << ", " << it->second[2] << endl;
    f.close();

/*
    //Permuta de palavras com sufixos -> palavras com mais de 5 letras
    //Combinação com sufixos de um sufixo com uma palavra
    #pragma omp parallel for reduction(+:found)
    for(int i = 0; i < sufixes.size(); i++)
    {
        //Pega uma palavra
        string st = sufixes.at(i)->st;
        //low_bound guarda o menor valor de palavra a ser combinada
        //se o sufixo tem 1 letra, a palavra a se combinar deve ter, ao menos, 5 letras
        int low_bound = st.size();
        if(low_bound < 6)
            low_bound = 5 - low_bound;

        //booleana que quebra o laco caso nao haja mais ocorrencias daquele sufixo
        bool no_more = false;
        //j inicial = menor tamanho permitido(low_bound)
        int j = low_bound;
        int up_bound = 10 - st.size();
        //Para todas as palavras de até 10 letras
        for( ; j < up_bound; j++)
        {
            //Combina uma a uma e tenta achar o resultado no dicionario (mapa correspondente)
            for(int k = 0; k < words_by_size[j].size(); k++)
            {
                //concatena sufixo com palavra
                string st_test = *words_by_size[j][k] + st;
                //verifica se encontrou
                map<string,int*>::iterator it_for = map_words_6to10.find(st_test);
                //Se encontrou
                if(it_for != map_words_6to10.end())
                {
                    //e palavra nao tinha sido encontrada anteriormente,
                    if(it_for->second[0] == 0)
                    {
                        //marca como encontrada
                        it_for->second[0]++;
                        //incrementa contador de encontradas
                        found++;
                        //decrementa ocorrencias
                        sufixes.at(i)->occurrences--;
                        //se não há mais ocorrencias
                        if(sufixes.at(i)->occurrences <= 0)
                        {
                            //quebra o laco
                            no_more = true;
                            break;
                        }
                    }
                }
            }
            //quebra laco caso nao haja mais ocorrencias
            if(no_more)
                break;
        }

        //continua com o mesmo processamento para palavras com 11 ou mais letras,
        //seguindo o mesmo padrao adotado anteriormente
        no_more = false;
        for(; j < words_by_size.size(); j++)
        {
            //Combina uma a uma e tenta achar o resultado no dicionario (mapa correspondente)
            for(int k = 0; k < words_by_size[j].size(); k++)
            {
                //concatena sufixo com palavra
                string st_test = *words_by_size[j][k] + st;
                map<string,int*>::iterator it_for = map_words_11plus.find(st_test);
                //Se encontrou
                if(it_for != map_words_11plus.end())
                {
                    //e palavra nao tinha sido encontrada anteriormente,
                    if(it_for->second[0] == 0)
                    {
                        //marca como encontrada
                        it_for->second[0]++;
                        //incrementa contador de encontradas
                        found++;
                        //decrementa ocorrencias
                        sufixes.at(i)->occurrences--;
                        //se não há mais ocorrencias
                        if(sufixes.at(i)->occurrences <= 0)
                        {
                            //quebra o laco
                            no_more = true;
                            break;
                        }
                    }
                }
            }
            //quebra laco caso nao haja mais ocorrencias
            if(no_more)
                break;
        }
    }
    cout << "Sufixos: found = " << found << endl;


    //Permuta de palavras com prefixos -> palavras com mais de 5 letras
    //Combinação com prefixos de um prefixo com uma palavra
    #pragma omp parallel for reduction(+:found)
    for(int i = 0; i < prefixes.size(); i++)
    {
        //Pega um prefixo
        string st = prefixes.at(i)->st;
        //low_bound guarda o menor valor de palavra a ser combinada
        //se o prefixo tem 1 letra, a palavra a se combinar deve ter, ao menos, 5 letras
        int low_bound = st.size();
        if(low_bound < 6)
            low_bound = 5 - low_bound;

        //booleana que quebra o laco caso nao haja mais ocorrencias daquele sufixo
        bool no_more = false;
        //j inicial = menor tamanho permitido(low_bound)
        int j = low_bound;
        int up_bound = 10 - st.size();
        //gera palavras de ate 10 letras
        for( ; j < up_bound; j++)
        {
            //Combina uma a uma e tenta achar o resultado no dicionario (mapa correspondente)
            for(int k = 0; k < words_by_size[j].size(); k++)
            {
                //concatena prefixo com palavra
                string st_test = st + *words_by_size[j][k];
                map<string,int*>::iterator it_for = map_words_6to10.find(st_test);
                //Se encontrou
                if(it_for != map_words_6to10.end())
                {
                    //e palavra nao tinha sido encontrada anteriormente,
                    if(it_for->second[0] == 0)
                    {
                        //marca como encontrada
                        it_for->second[0]++;
                        //incrementa contador de encontradas
                        found++;
                        //decrementa ocorrencias
                        prefixes.at(i)->occurrences--;
                        //se não há mais ocorrencias
                        if(prefixes.at(i)->occurrences <= 0)
                        {
                            //quebra o laco
                            no_more = true;
                            break;
                        }
                    }
                }
            }
            //quebra laco caso nao haja mais ocorrencias
            if(no_more)
                break;
        }

        for( ; j < words_by_size.size(); j++)
        {
            //Combina uma a uma e tenta achar o resultado no dicionario (mapa correspondente)
            for(int k = 0; k < words_by_size[j].size(); k++)
            {
                //concatena prefixo com palavra
                string st_test = st + *words_by_size[j][k];
                map<string,int*>::iterator it_for = map_words_11plus.find(st_test);
                //Se encontrou
                if(it_for != map_words_11plus.end())
                {
                    //e palavra nao tinha sido encontrada anteriormente,
                    if(it_for->second[0] == 0)
                    {
                        //marca como encontrada
                        it_for->second[0]++;
                        //incrementa contador de encontradas
                        found++;
                        //decrementa ocorrencias
                        prefixes.at(i)->occurrences--;
                        //se não há mais ocorrencias
                        if(prefixes.at(i)->occurrences <= 0)
                        {
                            //quebra o laco
                            no_more = true;
                            break;
                        }
                    }
                }
            }
            //quebra laco caso nao haja mais ocorrencias
            if(no_more)
                break;
        }
    }
    cout << "Prefixos: found = " << found << endl;
*/


/*
    f.open("prefix_after");
    cnt = 0;
    while(cnt < prefixes.size())
    {
        if(prefixes.at(cnt)->occurrences > 0)
        {
            f << prefixes.at(cnt)->st << " <- " << prefixes.at(cnt)->occurrences << endl;
            cnt++;
        }
        else
            prefixes.erase(prefixes.begin()+cnt);
    }
    f.close();

    cout << "Prefixos: found = " << found << endl;
*/


/*
    f.open("out.txt");
    //Impressão do mapa
 	for(it=map_words.begin(); it != map_words.end(); it++)
        f << it->first << " -> " << it->second[0] << ", "
          << it->second[1] << ", " << it->second[2] << endl;
    f.close();

    f.open("vector_out.txt");
    for(int i = 0; i < words_by_size.size(); i++)
    {
        int strvec_size = words_by_size[i].size();
        f << i+1 << " letra(s) (" << strvec_size << " palavras, " <<
         ((double)strvec_size/map_words.size()) << "% dos casos):" << endl;
        for(int j = 0; j < words_by_size[i].size(); j++)
            f << "[" << *words_by_size[i][j] << "] ";
        f << endl << endl << endl;
    }
    f.close();
*/


    map_words.clear();
    words_by_size.clear();
    size_of_words.clear();
    prefixes.clear();
    sufixes.clear();


    return 0;

}

